// 相比33题，这题中可以包含重复元素，则旋转后
// 可能出现[3,1,2,3,3,3,3], 这种nums[l] == nums[mid]的情况，无法判断target在哪一半
bool search(int* nums, int numsSize, int target){
    int l = 0, r = numsSize - 1;

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return true;

        if (nums[l] == nums[mid]) {
            l++;  // 去掉重复项
            continue;
        }
        if (target <= nums[numsSize - 1]) {   // target在右边
            if (nums[mid] <= nums[numsSize - 1]) {   // mid也在右边，正常二分
                if (nums[mid] > target) r = mid - 1;    // 在nums[x+1, mid]中
                else l = mid + 1;
            } else {    // mid在左边，直接逼近右边
                l = mid + 1;
            }
        }
        else {  // target在左边
            if (nums[mid] > nums[numsSize - 1]) { // mid也在左边，正常二分
                if (nums[mid] > target) r = mid - 1;// target在nums[0, mid]中
                else l = mid + 1;
            } else {    // mid在右边，直接逼近左边
                r = mid - 1;
            }
        }
    }
    return false;
}